import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Algorithm1{
 	static void Random(NewState1 state){
 		List<Planet> myPlanets = state.MyPlanets();
 		List<Planet> notMyPlanets = state.NotMyPlanets();
		Random random = new Random();
		int source = myPlanets.get(random.nextInt(myPlanets.size())).PlanetID();
		int dest = notMyPlanets.get(random.nextInt(notMyPlanets.size())).PlanetID();
		
		state.IssueOrder(source, dest);
	}

	static void BreadthFirst(NewState1 state, int heuristicNumber){
		int searchDepth = 3;
		List<List<NewState1>> stateTree = new ArrayList<List<NewState1>>();
		List<NewState1> levelOneFloor = new ArrayList<NewState1>();
		levelOneFloor.add(state);

		stateTree.add(levelOneFloor);

		int bestHeuristic = Integer.MIN_VALUE;
		NewState1 bestState = null;

		for (int i = 0; i < searchDepth; i++)
		{
			List<NewState1> currentFloor = stateTree.get(i);
			List<NewState1> nextFloor = new ArrayList<NewState1>();
			boolean endStateFound = false;
			for (NewState1 NewState2 : currentFloor)
			{
				// Hier voor de huidige state alle mogelijke volgende States toevoegen aan nextFloor
				for (Planet myPlanet : NewState2.MyPlanets())
				{ 
					//*Tikkeltje Efficienter denk ik
					for(Planet planet : NewState2.NotMyPlanets()){
						NewState1 stateToAdd = NewState2.clone();
						stateToAdd.setParent(NewState2);
						// Voer actie uit myPlanet valt neutralPlanet aan
						stateToAdd.SendFleet(myPlanet, planet);

						nextFloor.add(stateToAdd);
						int heuristic = stateToAdd.getScore(heuristicNumber);
						if (heuristic == Integer.MAX_VALUE)
						{
							// Eindstaat gevonden, stoppen met zoeken
							endStateFound = true;
							break;
						}
						else if (heuristic > bestHeuristic)
						{
							bestHeuristic = heuristic;
							bestState = stateToAdd;
						}
					}
					if (endStateFound)
						break;
				}
				if (endStateFound)
					break;
			}
			stateTree.add(nextFloor);
			if (endStateFound)
				break;
		}

		while (bestState.getParent() != state)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		//(3) Attack
		if (source != null && dest != null) {
			state.IssueOrder(source, dest);
		}
	}

	static void MinMax2(NewState1 pw, int heuristicNumber)
	{
		int searchDepth = 3;
		
		NewState1 bestState = MinMax2Recursion(pw, true, Integer.MAX_VALUE, searchDepth, heuristicNumber);
		while (bestState.getParent() != pw)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	private static NewState1 MinMax2Recursion(NewState1 state, boolean isMyTurn, int greek, int depth, int heuristicNumber)
	{	
		if (depth == 0)
			return state;

		int alpha = Integer.MIN_VALUE;
		int beta = Integer.MAX_VALUE;
		NewState1 bestState = state;
		for (NewState1 childState : state.getChildren(isMyTurn))
		{
			int greekNumber = isMyTurn ? alpha : beta;
			int childStateHeuristic = childState.getScore(heuristicNumber);
			if (childStateHeuristic == Integer.MAX_VALUE && isMyTurn) 
			{
				return childState;
			} 
			else if (childStateHeuristic == Integer.MIN_VALUE && !isMyTurn)
			{
				return childState;
			}
			NewState1 childResultState = MinMax2Recursion(childState, !isMyTurn, greekNumber, depth - 1, heuristicNumber);
			int heuristic = childResultState.getScore(heuristicNumber);
			if (isMyTurn)
			{
				if (heuristic > alpha)
				{
					bestState = childResultState;
					alpha = heuristic;
				}
				if (heuristic >= greek)
				{
					return bestState;
				}
			}
			else
			{
				if (heuristic < beta)
				{
					bestState = childResultState;
					beta = heuristic;
				}
				if (heuristic <= greek)
				{
					return bestState;
				}
			}
		}
		return bestState;
	}
	
	static List<NewState1> possibleEnemyActions = null;
	static NewState1 previousEnemyAction = null;
	static NewState1 previousState = null;
	static NewState1 previousFriendlyAction = null;
	
	static void AdaptToEnemy(NewState1 pw, int heuristicNumber)
	{
		int searchDepth = 3;
		
		// Find out what move enemy has made
		if (previousState != null)
		{
			String compareString = pw.toString();
			for (NewState1 enemyAction : possibleEnemyActions)
			{
				NewState1 prevStateClone = previousState.clone();
				prevStateClone.SendFleetParallel(previousFriendlyAction.preActionSource, previousFriendlyAction.preActionDest, enemyAction.preActionSource, enemyAction.preActionDest);
				
				if (compareString.equalsIgnoreCase(prevStateClone.toString()))
				{
					previousEnemyAction = enemyAction;
					break;
				}
			}
			// Change enemy heuristic based on possibleEnemyActions list and previousEnemyAction
			Heuristics1.adaptEnemyHeuristic(possibleEnemyActions, previousEnemyAction);
		}
		
		NewState1 bestState = ATERecursion(pw, true, Integer.MAX_VALUE, searchDepth, heuristicNumber);
		
		while (bestState.getParent() != pw)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		previousState = pw;
		previousFriendlyAction = bestState;
		possibleEnemyActions = pw.getChildren(false);
		
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	private static NewState1 ATERecursion(NewState1 state, boolean isMyTurn, int greek, int depth, int heuristicNumber)
	{	
		if (depth == 0)
			return state;

		int alpha = Integer.MIN_VALUE;
		int beta = Integer.MAX_VALUE;
		NewState1 bestState = state;
		for (NewState1 childState : state.getChildren(isMyTurn))
		{
			int greekNumber = isMyTurn ? alpha : beta;
			int childStateHeuristic = childState.getScore(heuristicNumber);
			if (childStateHeuristic == Integer.MAX_VALUE && isMyTurn) 
			{
				return childState;
			} 
			else if (childStateHeuristic == Integer.MIN_VALUE && !isMyTurn)
			{
				return childState;
			}
			NewState1 childResultState = MinMax2Recursion(childState, !isMyTurn, greekNumber, depth - 1, heuristicNumber);
			int heuristic = isMyTurn ? childResultState.getScore(heuristicNumber) : Heuristics1.enemyHeuristic(childResultState);
			if (isMyTurn)
			{
				if (heuristic > alpha)
				{
					bestState = childResultState;
					alpha = heuristic;
				}
				if (heuristic >= greek)
				{
					return bestState;
				}
			}
			else
			{
				if (heuristic < beta)
				{
					bestState = childResultState;
					beta = heuristic;
				}
				if (heuristic <= greek)
				{
					return bestState;
				}
			}
		}
		return bestState;
	}
	
	static enum Strategies{
		Attack, Reinforce, Expand, AttemptDirectExpansion
	}
	
	static Strategies lastAttack = null;
	static int amountAttacks = 1;
	static int Turn = 0;
	static void MultipleStrategy(NewState1 pw)
	{
		Turn++;
		// Check the current state and resolve what to do
		Strategies strategy = GetStrategy(pw);
		
		switch (strategy){
		case Attack:
			if (lastAttack != Strategies.Attack)
			{
				lastAttack = Strategies.Attack;
				amountAttacks = 1;
			} 
			else
			{
				amountAttacks++;
			}
			// Full on attack on the enemy
			Attack(pw);
			break;
		case AttemptDirectExpansion:
			if (lastAttack != Strategies.AttemptDirectExpansion)
			{
				lastAttack = Strategies.AttemptDirectExpansion;
				amountAttacks = 1;
			} 
			else
			{
				amountAttacks++;
			}
			// Take it to the direct expansion
			DirectExpansion(pw);
			break;
		case Reinforce:
			if (lastAttack != Strategies.Reinforce)
			{
				lastAttack = Strategies.Reinforce;
				amountAttacks = 1;
			} 
			else
			{
				amountAttacks++;
			}
			// Vulnerable friendly, save his ass
			Reinforce(pw);
			break;
		case Expand:
			if (lastAttack != Strategies.Expand)
			{
				lastAttack = Strategies.Expand;
				amountAttacks = 1;
			} 
			else
			{
				amountAttacks++;
			}
			Expand(pw);
			break;
		default:
			System.err.println("ERROR");
			break;
		}
	}
	
	static int VulnerableFriendly = -1;
	static int StrongFriendly = -1;
	static int ValuableEnemy = -1;
	static int StrongEnemy = -1;
	static int WeakEnemy = -1;
	static int ValuableNeutral = -1;
	static int TargetEnemy = -1;
	
	static Strategies GetStrategy(NewState1 pw)
	{
		VulnerableFriendly = -1;
		StrongFriendly = -1;
		ValuableEnemy = -1;
		StrongEnemy = -1;
		WeakEnemy = -1;
		ValuableNeutral = -1;
		TargetEnemy = -1;
		int enemyFleet = 0;
		int enemyGrowth = 0;
		int enemyPlanets = 0;
		int friendlyFleet = 0;
		int friendlyGrowth = 0;
		int friendlyPlanets = 0;
		Planet mostVulnerableFriendlyPlanet = null;
		Planet mostVulnerableEnemyPlanet = null;
		Planet mostValuableFriendlyPlanet = null;
		Planet mostValuableEnemyPlanet = null;
		Planet strongestFriendlyPlanet = null;
		Planet strongestEnemyPlanet = null;
		Planet bestNeutralPlanet = null;

		//*Eliminating double for loop make one instead
		for(Planet planet : pw.Planets()){
			switch (planet.Owner()) {
			case NewState1.NEUTRAL:
				if (bestNeutralPlanet != null)
				{
					if (bestNeutralPlanet.NumShips() > planet.NumShips())
					{
						if (bestNeutralPlanet.GrowthRate() / planet.GrowthRate() < (bestNeutralPlanet.NumShips() - planet.NumShips()) / 6)
						{
							bestNeutralPlanet = planet;
						}
					} 
					else
					{
						if (planet.GrowthRate() / bestNeutralPlanet.GrowthRate() > (planet.NumShips() - bestNeutralPlanet.NumShips()) / 6)
						{
							bestNeutralPlanet = planet;
						}
					}
				} else { bestNeutralPlanet = planet; }
				break;
			case NewState1.FRIENDLY:
				if (strongestFriendlyPlanet != null)
				{
					if (strongestFriendlyPlanet.NumShips() > planet.NumShips())
					{
						if (planet.GrowthRate() / strongestFriendlyPlanet.GrowthRate() > (strongestFriendlyPlanet.NumShips() - planet.NumShips()) / 6)
						{
							strongestFriendlyPlanet = planet;
						}
					} 
					else
					{
						if (strongestFriendlyPlanet.GrowthRate() / planet.GrowthRate() < (planet.NumShips() - strongestFriendlyPlanet.NumShips()) / 6)
						{
							strongestFriendlyPlanet = planet;
						}
					}
				} else { strongestFriendlyPlanet = planet; }
				if (mostVulnerableFriendlyPlanet != null)
				{
					if (mostVulnerableFriendlyPlanet.NumShips() + mostVulnerableFriendlyPlanet.GrowthRate() > planet.NumShips() + planet.GrowthRate()){
						mostVulnerableFriendlyPlanet = planet;
					}					
				}
				else { mostVulnerableFriendlyPlanet = planet; }
				if (mostValuableFriendlyPlanet != null)
				{
					if (mostValuableFriendlyPlanet.GrowthRate() < planet.GrowthRate()){
						mostValuableFriendlyPlanet = planet;
					}					
				}
				else { mostValuableFriendlyPlanet = planet; }
				friendlyPlanets++;
				friendlyFleet += planet.NumShips();
				friendlyGrowth += planet.GrowthRate();
				break;

			default:
				if (strongestEnemyPlanet != null)
				{
					if (strongestEnemyPlanet.NumShips() > planet.NumShips())
					{
						if (planet.GrowthRate() / strongestEnemyPlanet.GrowthRate() > (strongestEnemyPlanet.NumShips() - planet.NumShips()) / 6)
						{
							strongestEnemyPlanet = planet;
						}
					} 
					else
					{
						if (strongestEnemyPlanet.GrowthRate() / planet.GrowthRate() < (planet.NumShips() - strongestEnemyPlanet.NumShips()) / 6)
						{
							strongestEnemyPlanet = planet;
						}
					}
				} else { strongestEnemyPlanet = planet; }
				if (mostVulnerableEnemyPlanet != null)
				{
					if (mostVulnerableEnemyPlanet.NumShips() + mostVulnerableEnemyPlanet.GrowthRate() > planet.NumShips() + planet.GrowthRate()){
						mostVulnerableEnemyPlanet = planet;
					}					
				}
				else { mostVulnerableEnemyPlanet = planet; }
				if (mostValuableEnemyPlanet != null)
				{
					if (mostValuableEnemyPlanet.GrowthRate() < planet.GrowthRate()){
						mostValuableEnemyPlanet = planet;
					}					
				}
				else { mostValuableEnemyPlanet = planet; }
				enemyPlanets++;
				enemyFleet += planet.NumShips();
				enemyGrowth += planet.GrowthRate();
				break;
			}
		}
		// Set the static numbers
		ValuableEnemy = mostValuableEnemyPlanet.PlanetID();
		StrongEnemy = strongestEnemyPlanet.PlanetID();
		WeakEnemy = mostVulnerableEnemyPlanet.PlanetID();
		StrongFriendly = strongestFriendlyPlanet.PlanetID();
		VulnerableFriendly = mostVulnerableFriendlyPlanet.PlanetID();
		ValuableNeutral = bestNeutralPlanet.PlanetID();
		
		// Check if we can make a free move demolishing the enemy
		if (strongestEnemyPlanet.NumShips() / 2 < mostVulnerableFriendlyPlanet.NumShips())
		{
			// Enemy cannot conquer our weakest planet, attack an enemy planet.
			if (friendlyPlanets > enemyPlanets - 2 && Turn >= 2)
			{
				TargetEnemy = mostValuableEnemyPlanet.PlanetID();
				return Strategies.Attack;
			}
			else 
			{
				return Strategies.Expand;
			}
		}
		// Attack, Defend, Reinforce, Expand
		
		// See if our most vulnerable planet is in grave danger, if so, reinforce that Yedi!
		if (mostValuableFriendlyPlanet.NumShips() < mostVulnerableEnemyPlanet.NumShips() / 2)
		{
			if (strongestFriendlyPlanet == mostValuableFriendlyPlanet)
			{
				// Pretty much lost
				return Strategies.AttemptDirectExpansion;
			}
			else
			{
				// Reinforce most valuable from strongest
				VulnerableFriendly = mostValuableFriendlyPlanet.PlanetID();
				return Strategies.Reinforce;
			}
		}
		else if (mostValuableFriendlyPlanet.NumShips() < strongestEnemyPlanet.NumShips() / 2)
		{
			// A bit less in danger here, counterattack!
			if (friendlyPlanets >= 2)
			{
				if (strongestFriendlyPlanet == mostValuableFriendlyPlanet)
				{
					// Make the attack happen from the less valuable planet
					StrongFriendly = mostVulnerableFriendlyPlanet.PlanetID();
					TargetEnemy = strongestEnemyPlanet.PlanetID();
				}
			}
			return Strategies.Attack;
		}
		
		// At this point we know we our most vulnerable planet is safe, but we cannot simply demolish the enemy, weaken the enemy or strengthen ourselves?
		if (friendlyGrowth < enemyGrowth)
		{
			// Oh snap, better get our growth up, het liefst van hun mostValuable!
			if (mostValuableEnemyPlanet.NumShips() < strongestFriendlyPlanet.NumShips() / 2 - 1)
			{
				TargetEnemy = mostValuableEnemyPlanet.PlanetID();
				return Strategies.Attack;
			}
			return Strategies.AttemptDirectExpansion;
		}
		else
		{
			// Wreck the enemy while you're ahead!
			return Strategies.Attack;
		}
	}
	
	// Attack: If TargetEnemy >= 0 use TargetEnemy for target, otherwise decide between valuable, weak and strong enemy
	private static void Attack(NewState1 pw)
	{
		Planet source = null;
		Planet dest = null;
		
		if (TargetEnemy >= 0)
		{
			dest = pw.GetPlanet(TargetEnemy);
		}
		
		source = pw.GetPlanet(StrongFriendly);
		
		int fleetAvailable = source.NumShips() / 2;
		
		if (pw.GetPlanet(ValuableEnemy).NumShips() < fleetAvailable)
		{
			dest = pw.GetPlanet(ValuableEnemy);
		} 
		else if(pw.GetPlanet(StrongEnemy).NumShips() < fleetAvailable)
		{
			dest = pw.GetPlanet(StrongEnemy);
		} 
		else 
		{
			dest = pw.GetPlanet(WeakEnemy);
		}
		
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	// Expand: Try to target ValuableNeutral with your strongest, maybe some decisionmaking to be done here
	private static void Expand(NewState1 pw)
	{
		Planet source = null;
		Planet dest = null;
		
		source = pw.GetPlanet(StrongFriendly);
		
		// For now: Dest = ValuableNeutral, see how that works out.
		dest = pw.GetPlanet(ValuableNeutral);
		
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	// AttemptDirectExpansion: We NEED to capture a planet giving us some more strength, only option!
	private static void DirectExpansion(NewState1 pw)
	{
		Planet source = null;
		Planet dest = null;
		
		source = pw.GetPlanet(StrongFriendly);
		
		int fleetAvailable = source.NumShips() / 2;
		int minGrowth = 0;
		
		for(Planet p : pw.Planets()){
			switch (p.Owner()) {
			case NewState1.FRIENDLY:

				break;
			case NewState1.NEUTRAL:
				if (p.NumShips() < fleetAvailable)
				{
					if (p.GrowthRate() > minGrowth)
					{
						dest = p;
						minGrowth = p.GrowthRate();
					}
				}
				break;
			default:
				if (p.NumShips() < fleetAvailable)
				{
					if (p.GrowthRate() > minGrowth)
					{
						dest = p;
						minGrowth = p.GrowthRate();
					}
				}
				break;
			}
		}
		
		if (dest == null)
		{
			// Well fuck. (Nothing conquerable)
			dest = pw.GetPlanet(ValuableEnemy);
		}
	
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	// Reinforce: From strongestFriendly to VulnerableFriendly
	private static void Reinforce(NewState1 pw)
	{
		Planet source = null;
		Planet dest = null;
		
		source = pw.GetPlanet(StrongFriendly);
		dest = pw.GetPlanet(VulnerableFriendly);
		
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
}